package com.singzi.leetcode.N700;

import java.util.ArrayDeque;
import java.util.Deque;

public class T0678 {
}
class Solution0678 {
    public boolean checkValidString(String s) {
        Deque<Character> deque = new ArrayDeque<>();
        Deque<Character> starDeque = new ArrayDeque<>();

        for(int i = 0;i < s.length();i++){
            if(s.charAt(i) == '(' ) deque.push(s.charAt(i));
            else if(s.charAt(i) == '*'){
                starDeque.push(s.charAt(i));
            } else {
                if(deque.isEmpty() && starDeque.isEmpty()) return false;
                else if(!deque.isEmpty()){
                    deque.pop();
                }
                else starDeque.pop();
            }
        }
        while (!deque.isEmpty() && !starDeque.isEmpty()){
            int k = deque.pop();
            int x = starDeque.pop();
            if(k > x) return false;
        }
        return !deque.isEmpty();
    }
}